// 顺序栈

#pragma once

// 顺序栈的存储结构
template <typename E, int M>
struct SqStack
{
    E elem[M];
    int top;
};

// 初始化空栈 InitStack(&S)
template <typename E, int M>
void InitStack(SqStack<E, M> &S)
{
    S.top = 0;
}

// 入栈 Push(&S,e)
template <typename E, int M>
void Push(SqStack<E, M> &S, E e)
{
    // 若栈满，则抛出异常
    if (S.top == M)
        throw "stack full";
    // 否则，元素 e 插入栈顶
    S.elem[S.top++] = e;
}

// 出栈 Pop(&S,&e)
template <typename E, int M>
void Pop(SqStack<E, M> &S, E &e)
{
    //若栈空，则抛出异常
    if (S.top == 0)
        throw "stack empty";
    // 否则，删除栈顶元素并用 e 返回
    e = S.elem[--S.top];
}

// 取栈顶元素 GetTop(S,&e)
template <typename E, int M>
void GetTop(const SqStack<E, M> &S, E &e)
{
    // 若栈空，则抛出异常
    if (S.top == 0)
        throw "stack empty";
    // 否则，用 e 返回栈顶元素
    e = S.elem[S.top - 1];
}